#ifndef __BINARYTREE_HPP_
#define __BINARYTREE_HPP_

#include <iostream>
// #include <MyInclude/LinkQueue.h>

template<typename T>
class BinaryTree
{
public:

    BinaryTree();
    ~BinaryTree();

    void Insert(const T& element);
    void Remove(const T& element);
    T* Find(const T& element);
    // void show();

    template<typename U>
    friend std::ostream &operator<<(std::ostream& os, BinaryTree<U>& b);
    // template<typename U>
    // friend bool operator>(typename BinaryTree<U>::TreeNode *node,const U& element);

private:

    struct TreeNode
    {
        TreeNode(const T &element):data(element)
        {
            left = right = parent = nullptr;
        }
        T data;//数据域
        TreeNode *left;
        TreeNode *right;
        TreeNode *parent;
    };
    TreeNode* InsertNode(TreeNode *node,const T& element);
    void PrevTravel(TreeNode *node);
    void MidTravel(TreeNode *node);
    void PostTravel(TreeNode *node);
    void Free(TreeNode *node);
    TreeNode* RemoveNode(TreeNode *node,const T& element);
    TreeNode* GetMinNode(TreeNode *node);
    T* FindNode(TreeNode *node,const T& element);
    TreeNode* RotateRight(TreeNode *root);
    TreeNode* RotateLeft(TreeNode *root);
    TreeNode* RotateLeftRight(TreeNode *root);
    TreeNode* RotateRightLeft(TreeNode *root);
    int GetNodeHight(TreeNode *node);
    int LRDevition(TreeNode* node);
    TreeNode *root;
};



template<typename T>
BinaryTree<T>::BinaryTree()
{
    root = nullptr;
}

template<typename T>
BinaryTree<T>::~BinaryTree()
{
    Free(root);
}

template<typename T>
void BinaryTree<T>::Insert(const T &element)
{
    root = InsertNode(root,element);
}

template<typename T>
void BinaryTree<T>::Remove(const T &element)
{
    root = RemoveNode(root,element);
}

template<typename T>
T *BinaryTree<T>::Find(const T &element)
{
    return FindNode(root,element);
}

template<typename T>
typename BinaryTree<T>::TreeNode* BinaryTree<T>::InsertNode(TreeNode *node, const T &element)
{
    if(node == nullptr)
    {
        return new TreeNode(element);
    }

    if(node->data == element)
    {
        return node;
    }
    else if(node->data > element)
    {
        node->left = InsertNode(node->left,element);
        //左边重
        if(LRDevition(node) > 1)
        {
            //左左
            if(node->left->data > element)
            {
                //右旋
                node = RotateRight(node);
            }
            else
            //左右失衡
            {
                //左右旋
                node = RotateLeftRight(node);
            }
        }
    }
    else
    {
        node->right = InsertNode(node->right,element);
        //右边重
        if(LRDevition(node) < -1)
        {
             //右右
            if(node->right->data < element)
            {
               node = RotateLeft(node);

            }
            else
            //右左
            {
                node = RotateRightLeft(node);
            }
        }
    }
    return node;
    
}

// template<typename T>
// void BinaryTree<T>::show()
// {
//     std::cout<<"前序遍历:";
//     PrevTravel(root);
//     std::cout<<std::endl;

//     std::cout<<"中序遍历:";
//     MidTravel(root);
//     std::cout<<std::endl;
    
//     std::cout<<"后序遍历:";
//     PostTravel(root);
//     std::cout<<std::endl;

//     std::cout<<"层序遍历:";
//     LinkQueue q;
//     q.Push(root);
//     while(!q.IsEmpty())
//     {
//         TreeNode *node = (TreeNode*)*q.GetFront();
//         q.Pop();
//         std::cout<<node->data<<" ";
//         if(node->left)
//             q.Push(node->left);
//         if(node->right)
//             q.Push(node->right);
//     }
//     std::cout<<std::endl;
// }

template<typename T>
void BinaryTree<T>::PrevTravel(TreeNode *node)
{
    if(node == nullptr)
        return;
    std::cout<<node->data<<" ";
    PrevTravel(node->left);
    PrevTravel(node->right);
}

template<typename T>
void BinaryTree<T>::MidTravel(TreeNode *node)
{
     if(node == nullptr)
        return;
    
    MidTravel(node->left);
    std::cout<<node->data<<" ";
    MidTravel(node->right);
}

template<typename T>
void BinaryTree<T>::PostTravel(TreeNode *node)
{
     if(node == nullptr)
        return;
    PostTravel(node->left);
    PostTravel(node->right);
    std::cout<<node->data<<" ";
}

template<typename T>
void BinaryTree<T>::Free(TreeNode *node)
{
    if(node == nullptr)
        return; 
    Free(node->left);
    Free(node->right);
    delete node;
}

template<typename T>
typename BinaryTree<T>::TreeNode* BinaryTree<T>::RemoveNode(TreeNode *node, const T &element)
{
    if(node ==  nullptr)
        return nullptr;
    if(node->data < element)
    {
        node->right = RemoveNode(node->right,element);
    }
    else if(node->data > element)
    {
        node->left = RemoveNode(node->left,element);
    }
    else
    {
        //叶子
        if(node->left == nullptr && node->right == nullptr)
        {
            delete node;
            return nullptr;
        }
        else if(node->left && node->right )
        {
            //取右子树中最小结点
            TreeNode* minNode = GetMinNode(node->right);
            node->data = minNode->data;
            node->right = RemoveNode(node->right,minNode->data);
        }
        //有一个孩子
        else
        {
            TreeNode* child = node->left ? node->left : node->right;
            delete node;
            return child;
        }

    }
    //左边重
    if(LRDevition(node) > 1)
    {
        //左左
        if(LRDevition(node->left) > 0)
        {
            //右旋
            node = RotateRight(node);
        }
        else
        //左右失衡
        {
            //左右旋
            node = RotateLeftRight(node);
        }
    }
    if(LRDevition(node) < -1)
    {
            //右右
        if(LRDevition(node->right) < 0)
        {
            node = RotateLeft(node);

        }
        else
        //右左
        {
            node = RotateRightLeft(node);
        }
    }
    return node;
}

template<typename T>
typename BinaryTree<T>::TreeNode * BinaryTree<T>::GetMinNode(TreeNode *node)
{
    TreeNode *minNode = node;
    while(minNode->left)
        minNode = minNode->left;
    return minNode;
}

template<typename T>
T *BinaryTree<T>::FindNode(TreeNode *node,const T &element)
{
    if(node == nullptr)
        return nullptr;
    if(node->data == element)
        return &node->data;
    else if(node->data > element)
        return FindNode(node->left,element);
    else
        return FindNode(node->right,element);
}

template<typename T>
typename BinaryTree<T>::TreeNode *BinaryTree<T>::RotateRight(TreeNode *root)
{
    TreeNode *t = root->left;
    root->left = t->right;
    t->right = root;
    return t;
}

template<typename T>
typename BinaryTree<T>::TreeNode *BinaryTree<T>::RotateLeft(TreeNode *root)
{
    TreeNode *t = root->right;
    root->right = t->left;
    t->left = root;
    return t;
}

template<typename T>
typename BinaryTree<T>::TreeNode *BinaryTree<T>::RotateLeftRight(TreeNode *root)
{
    //左子树左旋
    root->left = RotateLeft(root->left);
    return RotateRight(root);//整棵树右旋
}

template<typename T>
typename BinaryTree<T>::TreeNode *BinaryTree<T>::RotateRightLeft(TreeNode *root)
{
    //右子树右旋
    root->right = RotateLeft(root->right);
    return RotateLeft(root);//整棵树左旋
} 

template<typename T>
int BinaryTree<T>::GetNodeHight(TreeNode *node)
{
    if(node == nullptr)
        return 0;
    int leftHight = GetNodeHight(node->left);
    int rightHight = GetNodeHight(node->right);
    return (leftHight > rightHight ? leftHight : rightHight) + 1;
}

template<typename T>
int BinaryTree<T>::LRDevition(TreeNode *node)
{
    if(node == nullptr)
        return 0;
    return GetNodeHight(node->left) - GetNodeHight(node->right);
}

template<typename T>
std::ostream& operator<<(std::ostream& os,BinaryTree<T>& b)
{
    // typename BinaryTree<T>::TreeNode *node = b.root;
    std::cout<<"前序遍历:";
    b.PrevTravel(b.root);
    std::cout<<std::endl;

    std::cout<<"中序遍历:";
    b.MidTravel(b.root);
    std::cout<<std::endl;

    std::cout<<"后序遍历:";
    b.PostTravel(b.root);
    std::cout<<std::endl;

    // std::cout<<"层序遍历:";
    // LinkQueue q;
    // q.Push(root);
    // while(!q.IsEmpty())
    // {
    //     TreeNode *node = (TreeNode*)*q.GetFront();
    //     q.Pop();
    //     std::cout<<node->data<<" ";
    //     if(node->left)
    //         q.Push(node->left);
    //     if(node->right)
    //         q.Push(node->right);
    // }
    return os;
}


// template <typename U>
// inline bool operator > (typename BinaryTree<U>::TreeNode *node,const U &element)
// {
//     return (node->data - element) == 0;
// }



#endif